'''
https://leetcode.cn/problems/triangle/?envType=study-plan-v2&envId=top-interview-150
'''
from functools import cache
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        @cache
        def f(i, j):
            if i == n:
                return 0
            p1 = f(i + 1, j)
            p2 = f(i + 1, j+1)
            return triangle[i][j] + min(p1, p2)
        return f(0, 0)

    def minimumTotal2(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0] * (n+1) for _ in range(n+1)]    # 下三角
        for i in range(n-1, -1, -1):
            for j in range(i, -1, -1):
                dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j+1])
        return dp[0][0]

    def minimumTotal3(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        A = [0] * (n+1)   # 下三角
        for i in range(n-1, -1, -1):
            B = [0] * (i+1)
            for j in range(i, -1, -1):
                B[j] = triangle[i][j] + min(A[j], A[j+1])
            A = B
        return A[0]
